package 题目集.二分;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/description/?envType=daily-question&envId=2024-10-02
 */
public class demo06准时到达的列车最小时速 {

    long[]dist;
    long hour;
    static final long base= (long) 100;

    public int minSpeedOnTime(int[] dist, double hour) {
        this.dist=new long[dist.length];
        /*放大base倍*/
        this.hour= Math.round(hour*base);
        long l = 1, r = this.hour;
        for (int i = 0; i < dist.length; i++) {
            this.dist[i]= base *dist[i];
            r=Math.max(r,this.dist[i]);
        }
        while (l <= r) {
            long m = l + r >> 1;
            if(check(m)){
                r=m-1;
            }else{
                l=m+1;
            }
        }
        if (l>1e7)return -1;
        return (int) l;
    }
    public boolean check(long m){
        long need=0;
        for (int i = 0; i < dist.length-1; i++) {
            long time = dist[i] / m;
            need+=time;
            need= (long) Math.ceil(1.0*need/base)*base;
            if (need>hour) return false;
        }
        /*最后一趟车不需要额外等*/
        long time = dist[dist.length-1] / m;
        need+=time;
        return need <= hour;
    }


    @Test
    public void client(){
        int[] dist={1,3,2};
        double hour=6;
        System.out.println(this.minSpeedOnTime(dist, hour));
    }
    @Test
    public void client2(){
        int[] dist={1,3,2};
        double hour=2.7;
        System.out.println(this.minSpeedOnTime(dist, hour));
    }
    @Test
    public void clien3(){
        int[] dist={1,3,2};
        double hour=1.9;
        System.out.println(this.minSpeedOnTime(dist, hour));
    }
    @Test
    public void clien4(){
        int[] dist={1,1,100000};
        double hour=2.01;
        System.out.println(this.minSpeedOnTime(dist, hour));
    }
}
